package imooc_math;

import java.util.Arrays;

public class MaxHeap {
		/*在这个堆的经典实现中，使用数组来存储数据，从下标为1开始计数。
		 * 子节点的下标分别是父节点下标的(2x)和(2x+1)
		 * 父节点下标=子节点下标/2
		 */	 	
		public static Comparable[] data;
	    public static int count;//数组中有多少元素
	    public int capacity;//容量--count可以达到的最大值
	    /*从1开始计数，用于存储数据的数组长度为capacity+1，数组下标为0的为空
	     * */
	    public MaxHeap(int capacity){
	        data=new Comparable[capacity+1];
	        count=0;
	        this.capacity=capacity;
	    }
	    public MaxHeap(Comparable[] arr){
	    	int n=arr.length;
	    	data=new Comparable[n+1];//数组长度：n+1,数组下标[0,n],其中用到的数据下标[1,n]
	    	for(int i=0;i<n;i++){
	    		data[i+1]=arr[i];
	    	}
	    	count=n;
	    	//从count/2开始shiftDown
	    	for(int i=count/2;i>=1;i--){
	    		shiftDown(i);
	    	}	
	    }
	    public int size(){
	        return count;
	    }
	    public static boolean isEmpty(){
	        return count==0;
	    }
	    public static void insert(Comparable a){
	    	
	    	data[++count]=a;
	        shiftUp(count);
	    }
	    public static void shiftUp(int count){
	        int k=count;
	        /*遇到的问题：交换之后是否可能产生父节点小与另一子节点的情况
	         *解决：当插入一个新的元素时，原来的堆本身就是符合父节点大于子节点的，所以当新插入的元素大于父节点时，他也就大于另一个子节点
	         * */
	        while(k>1&&data[k].compareTo(data[k/2])>0){//循环才能让他交换到最后，就是说如果他很大的话，一直比较到最高的节点
	        	//System.out.println(k);
	            swap(data,k,k/2);
	            k=k/2;
	        }
	        
	    }
	    public static Comparable extractMax(){
	    	Comparable ret = data[1];
	    	swap(data,1,count);
	    	count--;//直接count--，count处的数据并没有被抹除，会产生问题
	    	shiftDown(1);
	    	return ret;
	    }
	    //只与下标比k大的对比，确保父节点大于子节点
	    public static void shiftDown(int k){
	    	while(2*k<=count){
	    		int j=2*k;
	    		/*思想：先将子节点进行对比，找出最大的子节点；再将最大的子节点与父节点对比，如果子节点大的话就交换位置，否则退出循环
	    		 * shiftUp:a>b,c>a则c>b;shiftDown:b与c比较，用较大的与a比较，来确保把最大的放到父节点(a是父节点)
	    		 * */
	    		if(j+1<=count&&data[j+1].compareTo(data[j])>0){
	    			j=j+1;
	    		}
	    		if(data[k].compareTo(data[j])>=0){
	    			break;
	    		}
	    		swap(data,j,k);
	    		k=j;
	    	}

	    }
	    
	    public static  void swap(Comparable[] arry,int l,int r){
	        Comparable exchange=arry[l];
	        arry[l]=arry[r];
	        arry[r]=exchange;
	    }

	    /*public int extractMax(){
	    	int ret=shiftDown();
	    	
	    	return ret;
	    }*/
	    public static void main(String[] args){
	    	int n=50;
	       MaxHeap mh= new MaxHeap(n);
	       for(int i=0;i<n;i++){
	    	   mh.insert((int)(Math.random()*101));
	       }
	       /*System.out.println(mh.count);
	       System.out.println(Arrays.toString(data));*/
	       while(!isEmpty()){
	    	   System.out.print(extractMax()+" ");
	       }
	       
	    }
}
